//第十天错题

//2024年3月7日

#include <stdio.h>
#include <stdlib.h>
//1.传入-1，判断程序的结果
//-1
//原码 10000000000000000000000000000001
//反码 11111111111111111111111111111110
//补码 11111111111111111111111111111111
//-2
//原码 10000000000000000000000000000010
//反码 11111111111111111111111111111101
//补码 11111111111111111111111111111110
//-1 & -2 = -2
//    11111111111111111111111111111110
//    10000000000000000000000000000001
//    10000000000000000000000000000010
//-3
//原码 10000000000000000000000000000011
//反码 11111111111111111111111111111100
//补码 11111111111111111111111111111101
//-2 & -3 = -4
//    11111111111111111111111111111100
//    10000000000000000000000000000011
//    10000000000000000000000000000100
//
//由上述分析可知，每一次&运算，都会使-1的补码少一个1，而在32位下，-1的补码一共有32个1，故该循环执行32次，count的值为32
int func(int x)
{
	int count = 0;
	while (x)
	{
		count++;
		x = x & (x - 1);//与运算
	}
	return count;
}

int main()
{
	printf("%d", func(-1));
	return 0;
}

//2.
//对于右移运算符来说，二进制所有位数向右一位，最高位补符号位
//-1的补码全是1，右移一次，最高位补符号位1，所以x的补码一直是32个1，不会变成0，故该程序陷入死循环
int main()
{
	int count = 0;
	int x = -1;
	while (x)
	{
		count++;
		x = x >> 1;
	}
	printf("%d", count);
}

//3.不使用加减乘除实现两整数相加
int Add(int num1, int num2)
{
	while (num2 != 0)
	{
		int tmp = num1 ^ num2;
		num2 = (num1 & num2) >> 1;
		num1 = tmp;
	}
	return num1;
}

//4.找到所有数组中消失的数字
//利用哈希表
int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize)
{
	int* hash = (int*)malloc(sizeof(int) * (numsSize + 1));
	int i = 0;

	//将nums中有的元素，作为hash数组的下标进行存储，即如果hash中元素为1的下标就是原数组中的元素
	for (i = 0; i < numsSize; i++)
	{
		hash[nums[i]] = 1;
	}

	*returnSize = 0;
	for (i = 1; i <= numsSize; i++)
	{
		//如果hash[i] ！= 1，就说明该下标不是原数组的元素
		//将该下标作为元素从hash的头部开始存储，returnSize多大，就有多少个2符合要求的数
		if (hash[i] != 1)
		{
			hash[(*returnSize)++] = i;
		}
	}

	return hash;
}